For the convenience of the reader, various acronyms and other terms used in the field of this invention are defined at the end of the specification in a glossary. Other terms used by the applicant to define the operation of the inventive system are defined throughout the specification. For the convenience of the reader, applicant has added a number of topic headings to make the internal organization of this specification apparent and to facilitate location of certain discussions. These topic headings are merely convenient aids and not limitations on the text found within that particular topic.
In order to promote clarity in the description, common terminology for components is used. The use of a specific term for a component suitable for carrying out some purpose within the disclosed invention should be construed as including all technical equivalents which operate to achieve the same purpose, whether or not the internal operation of the named component and the alternative component use the same principles. The use of such specificity to provide clarity should not be misconstrued as limiting the scope of the disclosure to the named component unless the limitation is made explicit in the description or the claims that follow.
This invention relates to communications systems and methods, in particular, to packet communication systems and methods.
Mis-Ordering in Packet Communications Systems
Packet communication systems, or networks, are commonly used for the conveyance of information for data applications. However, packet networks are not perfect. While many systems are insensitive to absolute propagation delay (APDxe2x80x94the time it takes for a packet to propagate through the network), some systems are sensitive to propagation delay variation (PDVxe2x80x94changes in the APD, also known as jitter or wander).
If PDV varies enough from packet to packet, the packets may get re-ordered packets such that packet N, which was sent before packet N+1, arrives after packet N+1. An example of this mis-ordering is shown in FIG. 1.
FIG. 1A illustrates the general progression from transmit bits 1010 through encapsulation 1014 to transmit packets 1020 through the packet network 1024 to arriving packets 1030 through the JAB 1034 and de-encapsulation 1038 to become a stream of receive bits 1040. Consider a CBR (Constant Bit Rate) application where the bits are created at constant rate R. The rate R remains constant because there are no pauses in the data stream. The application at the receiving end is typically set to receive and process bits at the same rate R. On the path from creation to processing at the receive end the transmit bits 1010 first arrive at a device that encapsulates them into packets and injects the transmit packets 1020 into a packet network 1024 at rate P. Just as the bits arrive from the application at regular intervals (line 1010 of FIG. 1B), the encapsulating device 1014 sends out packets at regular interval (line 1020 of FIG. 1B). However, the intervening packet network is not perfect, so it introduces PDV due to congestion.
In general, the mis-ordering of packets does not impair data applications. This is because the communications software associated with these applications will re-order the packets as needed. However, packet communications systems can also be used for transport of data from applications that are not so forgiving. The mis-ordering of packets impairs these applications. Examples include:
Leased line applications transported via circuit emulation
Video applications
Certain data protocols such as SNA
The option exists for using software methods to correct the mis-ordering of packets but it may be impractical for certain applications. For example, a software-based approach requires large amounts of processor power, and may be impractical for high-bandwidth systems.
One prior art solution is disclosed in U.S. Pat. No. 6,134,246 for Inverse Multiplexing Within Asynchronous Transfer Mode Communication Networks. As described in connection with FIG. 11 of the ""246 patent, the patent teaches the use of a circular buffer to be used for re-synchronizing the packets based on an applied sequence number. The circular queue increments the position of the read pointer (head of the circular queue) and maintains a state variable (R_Seq_N) that indicates the sequence number of the next packet that should be read at the head of the circular queue. Incoming packets with sequence numbers in the range R_Seq_N to R_Seq_N+buffer size are processed. Packets with sequence numbers less than R_Seq_N are discarded as too late. Although the text in column 21 suggests that really early packets are discarded, the pseudo code indicates that the system handles packets with sequence numbers greater than R_Seq_N+buffer size by sending this early packet and all stored packet to the application and then setting R_Seq_N to be one sequence number larger than this really early packet. The net result is that a packet with a sequence number that is beyond R_Seq_N+buffer number results in that really early packet being processed but leads to the discarding of packets that are not unusually early.
To illustrate this point, consider a case with a buffer of eight addresses:
At time 1 the buffer contains data associated with addresses 2, 3, 4, and 6. The value of R_Seq_N is 105.
At time 2, an incoming packet arrives with sequence number 115. The system reacts by providing the packets with sequence numbers 105, 106, 107, 109, and 115 to the output port all at once, rather than at an even cadence.
After time 2, R_Seq_N is set to 116. Thus, when packets with sequence numbers 108, 110, 111, 112, 113, and 114 arrive, they are discarded as xe2x80x9ctoo latexe2x80x9d since the next expected packet sequence number is 116.
The sequence number 510 used in the ""246 patent is applied by the switching devices and is defined as a 32 bit integer. Thus, ""246 patent does not teach how to modify the control logic to handle the situation when the sequence number exceeds the maximum sequence number and restarts (wraps) with 0. Wrapping is to be expected for all practical applications
The method taught by the ""246 patent does not include monitoring the position of the buffer tail and thus any use of the buffer depth in a control system would require a separate operation to determine the range of active buffer addresses. The method taught by the ""246 patent is designed to ensure in-order packet delivery for non-time-critical packet traffic. Making the state machine synchronous with the incoming data is not a real drawback for this type of traffic, as it is bursty in nature and not time sensitive. The method of the ""246 patent is not readily extended to applications that call for draining packets from the buffer at a constant rate. Nor does this method provide filler for missing packets.
Thus, prior art solutions do not provide an efficient, robust means to correct the order of mis-ordered packets.
It is therefore an object of the invention to provide for the efficient correction of packet mis-ordering using sequence numbers and a circular buffer.
It is another object of the invention to provide for the correction of mis-ordered packets to increase the robustness of the service to the end user without adding significantly to the need for processing power to support the application.
These and other advantages of the present invention are apparent from the drawings and the detailed description that follows.
A circular buffer is used to receive packets transmitted to an application. Normally, incoming packets are placed at the xe2x80x9ctailxe2x80x9d of the buffer, which is indicated by the write pointer. Packets to be used by the application are read from the xe2x80x9cheadxe2x80x9d of the buffer, which is indicated by the read pointer. In contrast, the present invention uses the sequence number to direct the packets to specific places in the circular buffer. This inventive use of sequence number allows the packets to be written at the proper place in the buffer, regardless of the location of the write pointer. Within certain limits based on the size of the buffer, a packet that arrives out of sequence is not bound by the position of the write pointer to be placed into the buffer out of sequence.